// Created by WXX on 2021/12/8 20:48
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：48 ms, 在所有 C++ 提交中击败了30.00%的用户
 * 内存消耗：29.3 MB, 在所有 C++ 提交中击败了20.59%的用户
 */
class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int> &nums, int k) {

        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + nums[i - 1];
        vector<vector<int>> f(n + 2, vector<int>(4));

        int x = n + 1, y = 3;
        for (int i = n - k + 1; i; i--) {
            for (int j = 1; j <= 3; j++)
                f[i][j] = max(f[i + 1][j], f[i + k][j - 1] + s[i + k - 1] - s[i - 1]);
            if (f[x][3] <= f[i][3]) x = i;  // 因为要求字典序最小的方案，需要等于号
        }

        vector<int> res;
        while (y) {
            while (f[x][y] != f[x + k][y - 1] + s[x + k - 1] - s[x - 1]) x++;
            res.push_back(x - 1);
            x += k, y--;
        }
        return res;
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> nums = {1, 2, 1, 2, 6, 7, 5, 1};
    OutputBasicArray1D(Solution().maxSumOfThreeSubarrays(nums, 2));

    return 0;
}
